package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Arrays;
import java.util.Scanner;

/*
一个由N人组成的团体希望只用一艘船过河，最多只能载两个人。
因此，必须安排某种穿梭安排，以便来回划船，以便所有人都能通过。
每个人都有不同的赛艇速度；一对划船的人的速度是由较慢的一对的速度决定的。

你的工作是确定一个策略，最大限度地减少这些人沟通的时间。

输入
输入的第一行包含一个整数T（1<=T<=20），即测试用例的数量。
下面是每个案例：
每个案例的第一行是N，
第二行包含N个整数，给出每个人渡河的时间。
不会有超过1000人，也没有人需要超过100秒才能通过。

输出
对于每个测试用例，打印一行，其中包含所有N个人渡河所需的总秒数。

Sample Input
1
4
1 2 5 10
Sample Output
171
 */
public class b快速渡河by贪心 {
	public static void main(String[] args) {
		b快速渡河by贪心 test = new b快速渡河by贪心();
		test.useGreedyAlgorithmCrossRiver();
	}
	
	/**
	 * 前置方法
	 */
	public void useGreedyAlgorithmCrossRiver() {
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for (int i = 0; i < T; i++) {
			int length = scanner.nextInt();
			int[] speed = new int[length];
			for (int j = 0; j < length; j++) {
				speed[j] = scanner.nextInt();
			}
			Arrays.sort(speed);//排序很重要
			GreedyAlgorithmCrossRiver(length, speed);
		}
	}
	
	/**
	 * 迭代形式
	 * @param length
	 * @param speed
	 */
	public void GreedyAlgorithmCrossRiver(int length, int[] speed) {
		int people = length;
		int res = 0;
		while (people > 0) {
			if (people == 1) {
				res += speed[0];
				break;
			}
			if (people == 2) {
				res += speed[1];
				break;
			}
			if (people == 3) {
				res += (speed[2] + speed[0] + speed[1]);//这里为什么三个都加上；自己去推到，很容易推出来
				break;
			} else {//有两种策略：
				//先两个快的，最快的回来，再两个慢的，次快的回来
				int time1 = speed[1] + speed[0] + speed[people - 1] + speed[1];
				//一直使用最快的拉人
				int time2 = speed[people - 1] + speed[0] + speed[people - 2] + speed[0];
				res += Math.min(time1, time2);
				people -= 2;
			}
		}
		System.out.println(res);
	}
}
